# -*- coding: utf-8 -*-

import collections
import math
import pygame
import time
from pygame.locals import *

pygame.init()
global screen
screen = pygame. display.set_mode((500,500))


"""定义图"""
class Graph:
    def __init__(self):
        self.edges = {}

    def neighbors(self, id):
        return self.edges[id]

"""定义队列"""
class Queue:
    def __init__(self):
        self.elements = collections.deque()

    def empty(self):
        return len(self.elements) == 0

    def put(self, x):
        self.elements.append(x)

    """取出第一个元素"""
    def get(self):
        return self.elements.popleft()

"""广度优先算法实现"""
def breadth_first_search(graph, start, goal):
    froniter = Queue()
    froniter.put(start)
    came_from = {}
    came_from[start] = None
    # print(visited)
    visited = []

    while not froniter.empty():
        """先存入一个点"""
        current = froniter.get()
        # print("Visiting:", current)
        # time.sleep(0.3)
        # pygame.draw.rect(screen, (0,100,198), (current[0]*30, current[1]*30, 29, 29))
        # pygame.display.update()
        visited.append(current)

        if current == goal:
            break

        """再依次遍历邻居"""
        for next in graph.neighbors(current):
            if next not in came_from:
                froniter.put(next)
                came_from[next] = current
            # print(visited)
    return visited

def depth_first_search(graph, gg, start, goal):
    order = []
    visited = {}
    visited[start] = None
    def dfs(node):
        visited[node] = True
        order.append(node)

        if node == goal:
            print("break")
            return True

        for n in graph.neighbors(node):
            if not n in visited:
                if dfs(n) == True:
                    print n
                    return True

    for node in gg:
        if not node in visited:
            if dfs(node) == True:
                break


    return order



"""绘制地图"""
class SquareGrid():
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.walls = []

    def in_bounds(self, id):
        (x, y) = id
        return 0 <= x < self.width and 0 <=y < self.height

    def passable(self, id):
        return id not in self.walls

    def neighbors(self, id):
        (x, y) = id
        results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]
        if (x+y)%2 == 0:
            results.reverse()
        results = filter(self.in_bounds, results)
        results = filter(self.passable, results)
        return results

def draw_grid(grid, start, end):
    global screen
    g=[]
    width = grid.width
    height = grid.height

    gggg = []
    gggg.append(start)
    gggg.append(end)
    for x in range(width):
        for y in range(height):
            if (x,y) == start or (x,y) == end:
                pygame.draw.rect(screen, (255,142,150), (x*30, y*30, 29, 29))
            elif (x,y) not in DIAGRAM1_WALLS:
                pygame.draw.rect(screen, (143,241,198), (x*30, y*30, 29, 29))
                gggg.append((x,y))
            else:
                # pygame.draw.circle(screen, (0,0,198), (x*30, y*30+20), 10, 0)
                pass
    gggg.sort()
    return(gggg)

screen.fill((255,255,255))
g = SquareGrid(50,10)
# DIAGRAM1_WALLS=[(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(5,4),(5,5),(5,6),(5,7),(10,0)]
DIAGRAM1_WALLS=[(1,1),(1,2),(1,3),(1,4),(1,5),(5,4),(5,5),(5,6),(5,7),(10,0)]
g.walls = DIAGRAM1_WALLS
start = (0,1)
end = (7,3)
gg = draw_grid(g, start, end)

i=0
# cam = breadth_first_search(g,start,end)
cam = depth_first_search(g, gg, start, end)
clock = pygame.time.Clock()
while True:
    clock.tick(8)
    i+=1
    if i >= len(cam)-1:
        pass
    else:
        pygame.draw.rect(screen, (0,100,198), (cam[i][0]*30, cam[i][1]*30, 29, 29))

    for event in pygame.event.get():
        if event.type == QUIT:
            exit()

    pygame.display.update()





























